package com.dzu.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhaoDong
 * @date 2022/8/8 8:23
 * @description 409. 最长回文串
 * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
 *
 * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
 *
 *  
 *
 * 示例 1:
 *
 * 输入:s = "abccccdd"
 * 输出:7
 * 解释:
 * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 * 示例 2:
 *
 * 输入:s = "a"
 * 输入:1
 * 示例 3:
 *
 * 输入:s = "bb"
 * 输入: 2
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test409 {
    public static void main(String[] args) {
        int abccccdd = longestPalindrome("abccccdd");
        System.out.println(abccccdd);
    }


    /**
     * 「回文串」是指倒序后和自身完全相同的字符串，即具有关于中心轴对称的性质。观察发现，
     *
     * 当回文串长度为偶数时，则所有字符都出现了偶数次；
     * 当回文串长度为奇数时，则位于中心的字符出现了奇数次，其余所有字符出现偶数次；
     * 根据以上分析，字符串能被构造成回文串的充要条件为：除了一种字符出现奇数次外，其余所有字符出现偶数次。判别流程如下：
     *
     * 借助一个 HashMap ，统计字符串 s 中各字符的出现次数；
     * 遍历 HashMap ，统计构造回文串的最大长度，
     * 将当前字符的出现次数向下取偶数（即若为偶数则不变，若为奇数则减 1 ），出现偶数次则都可组成回文串，因此计入 res ；
     * 若此字符出现次数为奇数，则可将此字符放到回文串中心，因此将 odd 置 1 ；
     * 返回 res + odd 即可。
     *
     * 作者：jyd
     * 链接：https://leetcode.cn/problems/longest-palindrome/solution/409-zui-chang-hui-wen-chuan-by-jyd-ne80/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param s
     * @return
     */
    public static int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char str = s.charAt(i);
            map.put(str, map.getOrDefault(str, 0) + 1);
        }
        int res = 0;
        int odd = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            int rem = value % 2;
            res += value - rem;
            if (rem == 1) {
                odd = 1;
            }
        }
        return res + odd;
    }
}
